package demo.letcode.top100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 * 输入：digits = ""
 * 输出：[]
 * 示例 3：
 *
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 *
 * @author taqo
 * @date 2021/5/9
 */
public class _17电话号码的字母组合 {
    public static void main(String[] args) {
        String digits = "23";
        List<String> list = letterCombinations(digits);
        System.out.println(list);
    }

    private static List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        List<String> list = new ArrayList<>();
        def(list, map, digits, 0, "");
        return list;
    }

    private static void def(List<String> list, Map<Character, String> map, String digits, int idx, String contain) {
        if (idx == digits.length()) {
            list.add(contain);
            return;
        }
        String s = map.get(digits.charAt(idx));
        for (int i = 0; i < s.length(); i++) {
            def(list, map, digits, idx+1,contain+s.charAt(i));
        }
    }
}
